// Source : https://leetcode.com/problems/maximum-depth-of-binary-tree/
// Author : simba
// Date   : 2016-06-08

package main

import (
	"fmt"
)

type TreeNode struct {
	Left  *TreeNode
	Right *TreeNode
	data  int
}

//基于先序遍历创建二叉树
func create(index int, value []int) *TreeNode {
	var T *TreeNode = &TreeNode{}

	T.data = value[index-1]
	fmt.Printf("index %v \n", index)
	if (index < len(value)-1) && (2*index <= len(value)) && (2*index+1 <= len(value)) {
		T.Left = create(2*index, value)
		T.Right = create(2*index+1, value)
	}
	return T
}

func show(treeNode *TreeNode) {
	if treeNode != nil {
		fmt.Printf("%v ", treeNode.data)
		if treeNode.Left != nil {
			show(treeNode.Left)
		}
		if treeNode.Right != nil {
			show(treeNode.Right)
		}
	}
}

func maxDepth(root *TreeNode) int {
	var ld int = 0
	var rd int = 0
	var deep int = 0

	if root == nil {
		return 0
	}
	ld = maxDepth(root.Left)
	rd = maxDepth(root.Right)

	if ld > rd {
		deep = ld + 1
	} else {
		deep = rd + 1
	}

	return deep
}

func main() {
	//固定测试用例
	//       1
	//   2       3
	// 4   5   6   7
	value := []int{1, 2, 3, 4, 5, 6, 7}
	TreeRoot := create(1, value)
	show(TreeRoot) //先序
	fmt.Println("最大深度：", maxDepth(TreeRoot))
}
